This invention relates to a binary logic circuit for determining y=x mod(2m−1), where m>1, x is an n bit unsigned integer and n>m. In computing, the modulo operation (abbreviated as mod) finds the remainder of the Euclidean division of a number, called the dividend, by a divisor, called the modulus. Thus, in the expression y=x mod(2m−1), x is the dividend, 2m−1 is the modulus, and y is the remainder.
It is a common requirement in digital circuits that hardware is provided for calculating the value of x mod(2m−1) for some input x, where m is some constant known at design time. Often m will be the size of the number space so 2m−1 represents the largest number in that number space. For example, in a 16 bit unsigned number space, the smallest possible number is typically 0 and the largest possible number is 65535=216−1. Calculations of x mod(2m−1) are therefore frequently performed in digital logic and it is important to be able to perform them as quickly as possible so as to not introduce delay into the critical path of the circuit.
Binary logic circuits for calculating x mod(2m−1) are well known. For example, circuit design is often performed using tools which generate circuit designs at the register-transfer level (RTL) from libraries of logic units which would typically include a logic unit for calculating x mod(2m−1). Such standard logic units will rarely represent the most efficient logic for calculating x mod(2m−1) in terms of circuit area consumed or the amount of delay introduced into the critical path.